package chapter6;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并多个有序的集合
 *
 * @author yuh
 * @date 2018/4/20 13:01
 */
public class ListUtils {

    private ListUtils() {
    }

    /**
     * @param inputLists 多个有序集合,必须有序
     * @param <T>        必须实现Comparable
     * @return
     * @see Comparable
     */
    public static <T extends Comparable> List<T> mergeLists(List<List<T>> inputLists) {
        if (inputLists.size() % 2 != 0) {
            inputLists.add(new ArrayList<>());
        }
        if (inputLists.size() == 2) {
            return mergeTwoSortList(inputLists.get(0), inputLists.get(1));
        }
        List<List<T>> tmpLists = new ArrayList<>(2);
        for (int i = 0; i < inputLists.size(); i += 2) {
            tmpLists.add(mergeTwoSortList(inputLists.get(i), inputLists.get(i + 1)));
        }
        return mergeLists(tmpLists);
    }

    /**
     * 对两个已经排序数组进行归并
     *
     * @param aList 集合a
     * @param bList 集合b
     * @return
     */
    private static <T extends Comparable> List<T> mergeTwoSortList(List<T> aList, List<T> bList) {
        if (aList.isEmpty()) {
            return bList;
        }
        if (bList.isEmpty()) {
            return aList;
        }
        int aLength = aList.size();
        int bLength = bList.size();
        int i = 0;
        int j = 0;
        List<T> mergeList = new ArrayList<>(aLength + bLength);
        while (i < aLength || j < bLength) {
            if (i >= aLength) {
                mergeList.add(bList.get(j++));
            } else if (j >= bLength) {
                mergeList.add(bList.get(i++));
            } else if (aList.get(i).compareTo(bList.get(j)) > 0) {
                mergeList.add(bList.get(j++));
            } else {
                mergeList.add(aList.get(i++));
            }
        }
        return mergeList;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < 300; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < 10000; j++) {
                list.add(j);
            }
            lists.add(list);
        }
        long l = System.currentTimeMillis();
        //for (int i = 1; i < lists.size(); i++) {
        //    lists.get(0).addAll(lists.get(i));
        //}
        //Collections.sort(lists.get(0));
        List<Integer> lists1 = mergeLists(lists);
        long l1 = System.currentTimeMillis();
        System.out.println(l1 - l);
        //System.out.println(lists1);
        //System.out.println(lists1);
    }

}
